import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-04-04
 * Time: 12:46
 */


class TreeNode {
    int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode root;

    public TreeNode() {

    }

    public TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Test {

    /**
     * 1.同一棵树
     * https://leetcode.cn/problems/same-tree/description/
     */

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            //p、q都为空,认为是相同的树
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        //如果根节点的val不同
        if (p.val != q.val) {
            return false;
        } else {
            //判断左右子树是否相等
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    /**
     * 2.判断是否为子树
     * https://leetcode.cn/problems/subtree-of-another-tree/description/
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || isSameTree(root, subRoot);
    }


    /**
     * 3.翻转二叉树树
     * https://leetcode.cn/problems/invert-binary-tree/description/
     */

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /**
     * 4.二叉树的最大深度
     * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
     */

    public int maxDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
    }

    /**
     * 5.
     */

    // 优化之后
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return maxDepth(root) >= 1;
    }

    // 求树的高度(最大深度)
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int LeftH = maxDepth(root.left);
        if (LeftH < 0) {
            return -1;
        }
        int rightH = maxDepth(root.right);
        if (rightH < 0) {
            return -1;
        }
        if (Math.abs(LeftH - rightH) <= 1) {
            return Math.max(LeftH, rightH) + 1;
        } else {
            // 不平衡
            return -1;
        }
    }

    public boolean isBalanced2(TreeNode root) {
        if (root == null) {
            return true;
        }
        // int LeftH = maxDepth(root.left);左子树的高度
        // int rightH = maxDepth(root.right);右子树的高度
        return Math.abs(maxDepth1(root.left) - maxDepth1(root.right)) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    // 求树的高度(最大深度)
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
    }


    /**
     * 判断是否为对称二叉树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return false;
        }
        return isSymmetricofChild(root.left, root.right);
    }

    public boolean isSymmetricofChild(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null && right != null || left != null && right == null) {
            return false;
        }
        if (left.val == right.val) {
            // 左子树的左与右子树的右&&左子树的右与右子树的左对称
            return isSymmetricofChild(left.left, right.right) && isSymmetricofChild(left.right, right.left);
        } else {
            return false;
        }
    }

    //二叉树层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();// 要返回的
        Queue<TreeNode> queue = new LinkedList<>();// 队列
        if (root == null) {
            return ret;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }

    //方法1
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            // 情况1
            return root;
        }
        TreeNode LeftTree = lowestCommonAncestor1(root.left, p, q);// 递归左边
        TreeNode RightTree = lowestCommonAncestor1(root.right, p, q);// 递归右边
        if (LeftTree != null && RightTree != null) {
            return root;//情况2
        }
        if (LeftTree != null && RightTree == null) {
            return LeftTree;//情况3
        }
        if (LeftTree == null && RightTree != null) {
            return RightTree;//情况4
        }
        return null;
    }

    //方法2
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root, p, stackP);
        getPath(root, q, stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size > 0 && !stackP.isEmpty()) {
                stackP.pop();
                size--;
            }
        }
        if (sizeP < sizeQ) {
            int size = sizeQ - sizeP;
            while (size > 0 && !stackQ.isEmpty()) {
                stackQ.pop();
                size--;
            }
        }

        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek().equals(stackQ.peek())) {
                return stackP.peek();
            } else {
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }

    //root到node的路径结点
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        // 前序遍历
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean f1 = getPath(root.left, node, stack);
        if (f1) {
            return true;
        }
        boolean f2 = getPath(root.right, node, stack);
        if (f2) {
            return true;
        }
        stack.pop();
        return false;
    }


    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root, str);
        return str.toString();
    }

    private void tree2strChild(TreeNode root, StringBuilder str) {
        if (root == null) {
            return;
        }
        str.append(root.val);//处理根结点
        //处理左树
        if (root.left != null) {
            //root的左不为空
            str.append("(");//拼接左括号
            tree2strChild(root.left, str);//递归左树
            str.append(")");//拼接右括号
        } else {
            //root的左为空
            if (root.right == null) {
                //root右也为空
                return;
            } else {
                //root的右不为空
                str.append("()");
            }
        }
        //处理右树
        if (root.right == null) {
            return;
        } else {
            str.append("(");
            tree2strChild(root.right, str);
            str.append(")");
        }
    }

    public void preOrderNot(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }//左走完了
        //出栈顶元素
        TreeNode top = stack.pop();
        cur = top.right;
        //
        while (cur != null) {

        }
    }


}
